import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * Created by L.jp
 * Description:统计一个数字在排序数组中出现的次数。
 * User: 86189
 * Date: 2022-11-15
 * Time: 9:46
 */
public class Solution {
    //哈希表
   /* public int search(int[] nums, int target) {
        Map<Integer, Integer> map=new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(!map.containsKey( nums[i] )){
                map.put( nums[i],1 );
            }else{
                int count=map.get( nums[i] );
                count++;
                map.put(nums[i], count);
            }
        }
        return map.getOrDefault( target , 0 );
    }*/
    
    //二分查找，利用下标的差值来计算重复值的个数，当mid是目标值的之后，就看看左边界和右边界是不是一样的数，都是一样的那么就退出，说明找到了所有的重复数
    //如果左边界和右边界的数不和mid的值一样，那么就要不断缩减左右边界
   /* public int search(int[] nums, int target) {
        int left=0;
        int right=nums.length - 1;
        while (left < right) {
            int mid=left+(right - left)/2;
            if(nums[mid]>target){
                right = mid -1;
            }else if(nums[mid]< target){
                left=mid+1;
            }else {
                //找到了一个目标值就要看目标值在的区间是哪里
                if(nums[right]!=target){
                    //缩小目标值区间
                    right--;
                }else if( nums[left]!=target ){
                    left++;
                }else{
                    //边界都是目标值，那么就找到了
                    break;
                }
                
            }
        }
        return right-left+1;
    }*/
    
    
    //二分查找，计数
    public int search(int[] nums, int target) {
        int left=0;
        int right= nums.length-1;
        int count=0;
        while ( left<right ){
            int mid=left+(right-left)/2;
            if(nums[mid]<target){
                left = mid + 1;
            }else if(nums[mid]>= target){  //如果nums[mid]==target时只计数不处理下标那么会造成死循环
                right=mid;
            }
        }
        //此时left,mid，right处于同一个位，也就是一个target的位置，需要找出其他的target
        while ( left< nums.length && nums[left++]==target){
            count++;
        }
        return count;
    }
    
}
